/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2024-03-26
 * Time: 20:01
 */


public class Test1 {
    /**
     * 1.删除所以的val
     * https://leetcode.cn/problems/remove-linked-list-elements/description/
     */
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    /**
     * 2.翻转链表
     * https://leetcode.cn/problems/reverse-linked-list/
     */

    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }


    /**
     * 3.返回链表的中间结点
     * https://leetcode.cn/problems/middle-of-the-linked-list/description/
     */

    public ListNode middleNode(ListNode head) {

        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    /**
     * 4.返回倒数第k个结点的值
     * https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/
     */


    public int kthToLast(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < k - 1; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

    /**
     * 5.合并链表
     * https://leetcode.cn/problems/merge-two-sorted-lists/description/
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode l1 = list1;
        ListNode l2 = list2;
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode newHead = null;
        ListNode newTail = null;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                //
                if (newTail == null) {
                    newHead = newTail = l1;
                    l1 = l1.next;
                } else {
                    newTail.next = l1;
                    newTail = l1;
                    l1 = l1.next;
                }

            } else {
                if (newTail == null) {
                    newHead = newTail = l2;
                    l2 = l2.next;
                } else {
                    newTail.next = l2;
                    newTail = l2;
                    l2 = l2.next;
                }
            }
        }
        //
        if (l1 == null) {
            newTail.next = l2;
        } else {
            newTail.next = l1;
        }
        return newHead;
    }

    /**
     * 6.分割链表
     * https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
     */
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        if (pHead == null) {
            return null;
        }
        ListNode cur = pHead;
        ListNode LeftHead = null;//左边部分的头
        ListNode LeftTail = null;//左边部分的尾
        ListNode RightHead = null;//右边部分的头
        ListNode RightTail = null;//右边部分的尾
        while (cur != null) {
            if (cur.val < x) {
                if (LeftHead == null) {
                    //第一次插
                    LeftHead = LeftTail = cur;
                } else {
                    LeftTail.next = cur;
                    LeftTail = LeftTail.next;
                }
                cur = cur.next;
            } else {
                if (RightHead == null) {
                    //第一次插
                    RightHead = RightTail = cur;
                } else {
                    RightTail.next = cur;
                    RightTail = RightTail.next;
                }
                cur = cur.next;
            }
        }
        if (LeftHead == null) {
            return RightHead;
        }
        LeftTail.next = RightHead;
        if (RightHead != null) {
            RightTail.next = null;
        }
        return LeftHead;
    }

    /**
     * 返回公共结点
     * https://leetcode.cn/problems/intersection-of-two-linked-lists/
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode NodeA = headA;
        ListNode NodeB = headB;
        while (NodeA != NodeB) {
            if (NodeA == null) {
                NodeA = headB;
            } else {
                NodeA = NodeA.next;
            }
            if (NodeB == null) {
                NodeB = headA;
            } else {
                NodeB = NodeB.next;
            }
        }
        return NodeA;
    }

    /**
     * 判断是否为回文链表
     * https://leetcode.cn/problems/aMhZSa/
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        //
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode Newhead = reverseList(slow);
        ListNode tmp1 = head;
        ListNode tmp2 = Newhead;
        while (tmp2 != null) {
            //
            if (tmp2.val != tmp1.val) {
                return false;
            } else {
                tmp1 = tmp1.next;
                tmp2 = tmp2.next;
            }
        }
        return true;
    }

    //翻转链表
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
}
